package com.copa.l200;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author copa
 * @createDate 2022-05-23 09:42
 * @function BFS
 */
public class Test2 {

    public int numIslands(char[][] grid) {
        // 定义队列，如果扫到陆地则加入陆地坐标
        Queue<int[]> queue = new LinkedList();
        int row = grid.length;
        int col = grid[0].length;
        int result = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    // 该陆地坐标处理，将该坐标置为水地
                    grid[i][j] = '0';
                    result++;
                    // 发现新大陆后，将该坐标加入到队列中
                    queue.add(new int[]{i, j});
                    while (queue.size() != 0) {
                        // 如果队列不为0进行处理
                        int[] position = queue.poll();
                        int x = position[0];
                        int y = position[1];
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            // 往左检查是否为陆地，如果是加入队列并置为0，能加到队列证明就是陆地，不用担心那么早置为0的问题
                            // 那么早置为0也是为了降低时间复杂度，不然在leetcode过不了，会说 超出时间限制
                            queue.add(new int[]{x - 1, y});
                            grid[x - 1][y] = '0';
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            // 往上检查是否为陆地，如果是加入队列并置为0，能加到队列证明就是陆地，不用担心那么早置为0的问题
                            queue.add(new int[]{x, y - 1});
                            grid[x][y - 1] = '0';
                        }
                        if (x + 1 < row && grid[x + 1][y] == '1') {
                            // 往右检查是否为陆地，如果是加入队列并置为0，能加到队列证明就是陆地，不用担心那么早置为0的问题
                            queue.add(new int[]{x + 1, y});
                            grid[x + 1][y] = '0';
                        }
                        if (y + 1 < col && grid[x][y + 1] == '1') {
                            // 往下检查是否为陆地，如果是加入队列并置为0，能加到队列证明就是陆地，不用担心那么早置为0的问题
                            queue.add(new int[]{x, y + 1});
                            grid[x][y + 1] = '0';
                        }
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        };
        System.out.println(new Test2().numIslands(grid));
    }
}

